package leetcode.每日一题;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author ：zsy
 * @date ：Created 2021/6/11 20:23
 * @description：
 */
public class 完全平方数 {
    public static void main(String[] args) {

    }

    @Test
    public void Test() {
        Solution solution = new Solution();
        System.out.println(solution.numSquares(297));
    }

    class Solution {
        int min = Integer.MAX_VALUE;
        int[] memo;
        public int numSquares(int n) {
            memo = new int[n + 1];
            Arrays.fill(memo, Integer.MAX_VALUE);
            dfs(n, 0);
            return min;
        }

        public void dfs(int n, int count) {
            if (count > memo[n]) return;
            if(n == 0) {
                min = Math.min(min, count);
                return;
            }
            memo[n] = count;
            int sqrt = (int) Math.sqrt(n);
            int i = 1;
            for(; i <= sqrt; i++) {
                dfs(n - i * i, count + 1);
            }
        }

        public int sqrt(int num) {
            int l = 0;
            int r = num;
            int mid;
            int ans = -1;
            while(l <= r) {
                mid = (l + r) >> 1;
                if((long) mid * mid <= num) {
                    ans = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            return ans;
        }
    }
}
